package string;

/**
 * 给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
 * 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
 * <p>
 * 示例 1：
 * 输入：s = "abcabc"
 * 输出：10
 * 解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
 * <p>
 * 示例 2：
 * 输入：s = "aaacb"
 * 输出：3
 * 解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
 * <p>
 * 示例 3：
 * 输入：s = "abc"
 * 输出：1
 *
 * @author Jisheng Huang
 * @version 20250427
 */
public class NumOfSubstr_1358 {
    /**
     * 从小到大枚举子串右端点 right，同时用哈希表/数组统计每种字母的出现次数。如果子串符合要求（三种字母都至少出现一次），则右移左端点
     * left，直到不符合要求为止。
     * <p>
     * 内层循环结束后，[left,right] 这个子串是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。
     * 由于子串越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。
     * 也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子串都是满足要求的，这一共有 left 个，加到答案中。
     *
     * @param s the given string
     * @return the number of string that a, b, c only appear at least once
     */
    public static int numberOfSubstrings(String s) {
        char[] arr = s.toCharArray();
        int ans = 0;
        int left = 0;
        int[] cnt = new int[3];

        for (char c : arr) {
            ++cnt[c - 'a'];

            while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
                --cnt[arr[left] - 'a'];
                ++left;
            }

            ans += left;
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(numberOfSubstrings("abcabc"));
        System.out.println(numberOfSubstrings("aaacb"));
        System.out.println(numberOfSubstrings("abc"));
    }

}
